package com.example.leetdemo.process;

import java.util.Stack;

public class Solution907 {

    public int sumSubarrayMins(int[] arr) {
        Stack<Integer> lSt = new Stack<>(), rSt = new Stack<>();
        int[][] dp = new int[arr.length][2];

        for (int i = 0; i < arr.length; i++) {
            if (lSt.size() == 0) {
                lSt.add(i);
                dp[i][0] = 1;
            } else {
                while (lSt.size() > 0) {
                    if (arr[lSt.peek()] <= arr[i]) {
                        break;
                    }
                    lSt.pop();
                }
                dp[i][0] = lSt.size() > 0 ? i - lSt.peek() : i + 1;
                lSt.add(i);
            }
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            if (rSt.size() == 0) {
                rSt.add(i);
                dp[i][1] = 1;
            } else {
                while (rSt.size() > 0) {
                    if (arr[rSt.peek()] < arr[i]) {
                        break;
                    }
                    rSt.pop();
                }
                dp[i][1] = rSt.size() > 0 ? rSt.peek() - i : arr.length - i ;
                rSt.add(i);
            }
        }
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            count = (count + ((dp[i][0] * dp[i][1]) % 1000000007 ) * arr[i]) % 1000000007;
        }
        return count;
    }

}
